﻿// Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm (find it in Wikipedia).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _11BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            // Reading an array form the console.
            Console.Write("Array size:");
            string strArraySize = Console.ReadLine();
            int arraySize = int.Parse(strArraySize);
            int[] array = new int[arraySize];
            for (int i = 0; i <= array.Length - 1; i++)
            {
                Console.Write("array[{0}]:", i);
                string strValue = Console.ReadLine();
                array[i] = int.Parse(strValue);
            }
            Console.WriteLine("The mixed array looks like this:");
            foreach (var item in array)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            
            // Sorting it so we can apply the binary search.
            for (int i = 0; i <= array.Length - 2; i++)
            {
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[i] > array[j])
                    {
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
            Console.WriteLine("The sorted array looks like this:");
            foreach (var item in array)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
            
            //The binary search part.
            Console.Write("Enter the value of the element that we are going to serach for:");
            string strElement = Console.ReadLine();
            int element = int.Parse(strElement);
            int start = 0, end = array.Length - 1, middle = (start + end) / 2;
            while (start <= end)
            {
                middle = (start + end) / 2;
                if (element == array[middle])
                {
                    Console.WriteLine("Found it at array[{0}]!", middle);
                    return;
                }
                else if (element < array[middle])
                {
                    end = middle - 1;
                }
                else if (element > array[middle])
                {
                    start = middle + 1;
                }
            }
            Console.WriteLine("Not Found!");

        }
    }
}
